Năm 1996 người dân Israel lần đầu tiên trực tiếp bầu ra thủ tướng của mình. Netanyahu đã thuê nhà điều hành chiến dịch chính trị Cộng hoà Mỹ Arthur Finkelstein chỉ đạo chiến dịch tranh cử của mình, và dù mang phong cách tranh cử kiểu Mỹ và những lời chỉ trích mạnh mẽ từ phía bên trong Israel, nó vẫn chứng minh là có hiệu quả. (Cách thức này sau đó đã được Ehud Barak copy lại trong chiến dịch tranh cử năm 1999 và đánh bại Netanyahu.) Netanyahu giành thắng lợi, làm ngạc nhiên nhiều người khi đánh bại ứng cử viên được ưa chuộng trước cuộc bầu cử là Shimon Peres. Nguyên nhân chính dẫn tới sự thất bại của Peres là một làn sóng những vụ đánh bom tự sát ngay trước cuộc bầu cử; ngày 3 và 4 tháng 3 năm 1996, người Palestine đã tiến hành hai vụ đánh bom tự sát, làm thiệt mạng 32 người Israel, và Peres dường như không có khả năng ngăn chặn những vụ tấn công. Không như Peres, Netanyahu không tin tưởng Yasser Arafat và đặt điều kiện bất kỳ tiến bộ nào trong tiến trình hoà bình đều phải đi kèm với việc Chính quyền Quốc gia Palestine thực hiện các nghĩa vụ của mình – chủ yếu chiến đấu chống chủ nghĩa khủng bố, và tranh cử với khẩu hiệu "Netanyahu - tạo lập một nền hoà bình an toàn". Tuy nhiên, dù Netanyahu chiến thắng và trở thành thủ tướng, Công Đảng giành thắng lợi trong cuộc bầu cử Knesset, đánh bại liên minh Likud–Gesher–Tzomet, đồng nghĩa với việc Netanyahu phải dựa trên một liên minh với các đảng chính thống cực đoan, Shas và UTJ (các chính sách an sinh xã hội của các đảng này công khai đối lập với mục tiêu tư bản của ông) để cầm quyền.

Ngay khi được bầu, Netanyahu là người trẻ nhất trong lịch sử giữ chức vụ này. Ông có một mối quan hệ không vững chắc với Tổng thống Hoa Kỳ Bill Clinton, người đã có một số lưu ý rất không thuận lợi với ông trước sự hiện diện của Aaron David Miller.[20] Người phát ngôn Nhà Trắng ở thời điểm đó Joe Lockhart, người miêu tả Netanyahu trong một cuộc phỏng vấn là "một trong những cá nhân khó chịu nhất bạn sắp phải gặp - một kẻ nói phét và lừa đảo. Ông ta có thể mở miệng và bạn có thể không có lòng tin rằng bất kỳ điều gì phát ra từ nó là sự thật."[20]

Với tư cách thủ tướng, Netanyahu đã đàm phán với Yasser Arafat trong khuôn khổ Hiệp ước Sông Wye.[21] Không có tiến bộ nào trong những cuộc đàm phán với người Palestine, và dù họ không thể thực hiện được những bước đã thoả thuận trong Hiệp định Oslo, Netanyahu đã chuyển giao hầu hết quyền tài phán của Hebron cho người Palestine. Năm 1996, Netanyahu và thị trưởng Jerusalem Ehud Olmert quyết định mở một lối ra cho Western Wall Tunnel.[22] Việc này đã dẫn tới những cuộc bạo loạn kéo dài ba ngày của người Palestine, khiến cả người Israel và người Palestine thiệt mạng.[23]

Với tư cách thủ tướng Netanyahu nhấn mạnh một chính sách "ba không": không rút quân khỏi Cao nguyên Golan, không đàm phán trường hợp Jerusalem, không đàm phán với bất kỳ điều kiện tiên quyết nào.[24]

Netanyahu bị phe chính trị cánh tả tại Israel phản đối và cũng mất sự ủng hộ của cánh hữu bởi những nhượng bộ của ông cho người Palestine ở Hebron và những nơi khác, và vì những cuộc đàm phán với Arafat của ông nói chung. Sau một chuỗi các scandal dài (gồm cả những chuyện tầm phào về cuộc hôn nhân của ông) và một cuộc điều tra về những cáo buộc tham nhũng (sau này đã được tuyên trắng án), Netanyahu mất sự ủng hộ của người dân Israel.

Sau khi bị Ehud Barak đánh bại trong cuộc bầu cử thủ tướng năm 1999, Netanyahu tạm thời rút lui khỏi chính trị.[13]